package alo.p6.work;

import alo.p6.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

//二叉树深度
public class HeightOfBinaryTree {
    //递归
    int heightBinaryTree(BinaryTreeNode root){
        int leftheight,rightheight;
        if (root==null) return 0;
        else {
            leftheight=heightBinaryTree(root.getLeft());
            rightheight=heightBinaryTree(root.getRight());
            return leftheight>rightheight? leftheight+1 :rightheight+1;
        }
    }
    //非递归
    int heightBinaryTree2(BinaryTreeNode root){
        int level=1;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        if (root==null) return 0;
        queue.offer(root);
        //一层结束，加一个null
        queue.offer(null);
        while (!queue.isEmpty()){
            root=queue.poll();
            //root==null代表上一层的所有孩子都进入队列（即这一层所以的结点都进入队列）
            //操作为加一个间隔null，层数加1
            if (root==null){
                if (!queue.isEmpty()) queue.offer(null);
                level++;
            }else {
                if (root.getLeft()!=null) queue.offer(root.getLeft());
                if (root.getRight()!=null) queue.offer(root.getRight());
            }
        }
        return level;
    }
}
